import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 哈希链表
 * @param <K>
 * @param <V>
 */
public class MyLinkedHashMap<K, V> {

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        Node<K, V> prev;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final Node<K, V> head, tail;

    private final HashMap<K, Node<K, V>> map = new HashMap<>();

    public MyLinkedHashMap() {
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

   public V get(K key) {
       Node<K, V> node = map.get(key);
       if (node != null) {
           return node.value;
       }
       return null;
   }

   public void put(K key, V value) {
        // 若为新插入的节点，则同时插入链表和map
       if (!map.containsKey(key)) {
           // 插入新的Node
           Node<K, V> node = new Node<>(key, value);
           addLastNode(node);

       }

       // 若存在，则替换之前的value
       map.get(key).value = value;
   }

   public void remove(K key) {
        // 若key不存在，直接返回
       if (!map.containsKey(key)) {
           return;
       }
       // 若key存在，则需要同时删除链表和哈希表中的节点
       Node<K, V> node = map.get(key);
       map.remove(key);
       removeNode(node);
   }

   public boolean containsKey(K key) {
        return map.containsKey(key);
   }

   public List<K> getKeys() {
       ArrayList<K> list = new ArrayList<>();
       for (Node<K, V> p = head.next; p != tail; p = p.next) {
           list.add(p.key);
       }
       return list;
   }

   public int size() {
        return map.size();
   }

   private void addLastNode(Node<K, V> x) {
        Node<K, V> temp = tail.prev;
        x.next = tail;
        x.prev = temp;
        temp.next = x;
        tail.prev = x;
   }

   private void removeNode(Node<K, V> x) {
       Node<K, V> next = x.next;
       Node<K, V> prev = x.prev;
       prev.next = next;
       next.prev = prev;
   }

    public static void main(String[] args) {

    }

}
